package com.algrithom.sort.insertsort;

import java.util.Arrays;

/**
 * 折半插入排序
 *
 * @author think
 * @version 1.0.0
 * @since 2020/1/1
 */
public class BsSort {
    
    public static void main(String[] args){
        int[] array = {1,3,4,2,1,10,5,12,13,14,11};
        binaryInsertSort(array);
        System.out.println(Arrays.toString(array));
    }
    
    /**
     * 折半插入排序
     *
     * @param a 待排序数组
     */
    public static void binaryInsertSort(int[] a){
        int len = a.length - 1;
        for (int i = 1; i <= len; i++) {
            int temp = a[i];
            
            int low = 0;
            int middle;
            int high = i - 1;
            while (low <= high) {
                middle = (low + high) / 2;
                if (temp < a[middle]) {
                    high = middle - 1;
                } else {
                    low = middle + 1;
                }
            }
            
            for (int k = i - 1; k >= low; k--) {
                a[k + 1] = a[k];
            }
            
            a[low] = temp;
        }
    }
}
